<html>
<head>
<script language="javascript">
<!--
    var endtime;
    
    function initcount(secondsleft) {
        var now = new Date();
        return now.getTime() + secondsleft*1000;
    }
    function count1(i) { i = i - i%1; return i; } 
    function count2(i) { i = i - i%1; if (i < 10) return "0"+i; return i; }
    function updateclock(head, word, endtime) {
        var now = new Date();
        var delta = (endtime - now.getTime())/1000;
        var s, x;
        if(delta < 1)
            s = head + " has ended";
        else{
            s = head + " ends: ";
            s = head + ": ";
            if(delta >= 24*3600)
                s = s + count1(delta/86400) + "d ";
            if(delta >= 3600)
                s = s + count2((delta/3600)%24) + "h ";
            if(delta >= 60)
                s = s + count2((delta/60)%60) + "m ";
            s = s + count2(delta%60) + "s";
            setTimeout("updateclock('"+head+"','"+word+"',"+endtime+")", 500);
        }

        var slot = document.getElementById(word);
        slot.innerHTML = s;
    }
-->
</script>

<title>USACO Problems</title>
</head>
<body onload="endtime = initcount(344509); updateclock('U S OPEN,  2006', 'Contest', endtime); endtime = initcount(14400); updateclock('Your Contest Session', 'Person', endtime);" background='/usaco/bg9.jpg'>

<table><tr>
<td><img src='/usaco/cowhead2.gif' width='65' height='81'>
</td>
<td valign='top'>
<table cellpadding=0 cellspacing=0>
    <tr><td>OPEN06</td></tr>
    <tr><td><div id='Contest'></div></td></tr>
    <tr><td><div id='Person'></div></td></tr>
    <tr><td></td></tr>
</table>
<td></tr>
</table>


<pre></pre>
<pre>**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Five problems numbered 11 through 15
**********************************************************************

Problem 11: Bedtime Reading, I [Traditional, 2006]

Farmer John was performing his nightly bedtime reading duties for
Bessie. "Oh, this gives me a headache," moaned Bessie.

"But it's just simple number theory," replied FJ. "Let's go over
it again. The sigma function of a number is just the sum of the
divisors of the number. So, for a number like 12, the divisors are
1, 2, 3, 4, 6, and 12. Summing them we get 28."

"That's all there is to it?" asked Bessie.

"Yep." replied FJ. "Perhaps someone will write a program to calculate
the sigma function of an integer I (1 &lt;= I &lt;= 1,000,000)."

PROBLEM NAME: br1

INPUT FORMAT:

* Line 1: A single integer, I

SAMPLE INPUT (file br1.in):

12

OUTPUT FORMAT:

* Line 1: The sum of all of I's divisors.

SAMPLE OUTPUT (file br1.out):

28

**********************************************************************

Problem 12: Eenie Meenie Miney Moe [Rob Kolstad, 2006]

"Eenie, meenie, miney, moe... catch a heifer by the toe," an
exasperated Bessie muttered. She could never get the syllables right
when choosing calves for game playing. Today she is trying to see
which of N (1 &lt;= N &lt;= 2,300) heifers conveniently numbered 1..N
will get a special hunk of hay made from tender spring grass.

Thus, Bessie is leaving it up to you. You will be provided a list
of integers. This list is of length L (1 &lt;= L &lt;= 10) and describes
a sort of "elimination sequence" containing integers in the range
(1..N). If the N heifers are lined up in order in a circle, then
the elimination count starts at heifer number 1. The L<sub>1</sub>th
heifer is eliminated. Start at the next heifer, the count proceeds
for L<sub>2</sub> more heifers to find the baby cow to be eliminated.
Both the line of heifers and the elimination sequence are circular,
wrapping around as necessary.

By way of example, consider a set of 8 heifers and an elimination
sequence of {5, 3}. Initially, the 8 heifers form a circle as
shown in Figure A.
<img src="/eenie.gif">

Starting at heifer 1, count 5 cows and eliminate the 5th one (Figure
B). Now count 3 more and eliminate the 3rd cow, which is number 8
(Figure C).

The elimination list is exhausted so it is recycled. Count five
more heifers and eliminate the fifth one, which is number 6 (Figure
D) since number 5 is no longer present. Now count three more to
eliminate the third cow, number 2 (Figure E). Recycle the list and
count five more to eliminate number 3 (Figure F). Count three more
to eliminate number 1 (Figure G), and finally count five more to
eliminate number 4 (Figure H).

Heifer 7 is left standing.

PROBLEM NAME: eenie

INPUT FORMAT:

* Line 1: Two space-separated integers: N and L

* Line 2: L space-separated integers (range 1..N) that respectively
        compose the elimination sequence.

SAMPLE INPUT (file eenie.in):

8 2
5 3

OUTPUT FORMAT:

* Line 1: A single integer that is the number of the heifer left
        standing (who will receive the special hay treat)

SAMPLE OUTPUT (file eenie.out):

7

**********************************************************************

Problem 13: Cow Pizza [Traditional, 2006]

Oh how the cows love their pizza! Even though they are picky, they
do love variety, too. They order from the local pizza parlor that
features T (1 &lt;= T &lt;= 20) different toppings in addition to a 
complete set of soft drinks and healthy salads.

The toppings are conveniently numbered 1..T so the cows can order
by number. Your job is to calculate how many possible pizzas can
be created given that some cows will not tolerate various combinations
of toppings (e.g., some cows simply will not eat Anchovies or the 
combination of Mushrooms and Asparagus).
 
Given a set of N (1 &lt;= N &lt;= 52) constraints, figure out how many 
pizzas can be made using all possible combinations of the ingredients 
(which, of course, includes no ingredients at all). Each constraint is
a set of numbers of size 1..T that lists the ingredients that disqualify
a pizza from being considered. 
 
A constraint like "5 3" means that no pizza can contain ingredient    
#5 and also ingredient #3. This means a pizza with ingredients 3,
5, and 6 will not be counted as acceptable.

PROBLEM NAME: pizza

INPUT FORMAT:

* Line 1: Two space-separated integers: T and N

* Lines 2..N+1: Each line describes a constraint using space-separated
        integers. The first integer is the number of ingredients in
        the constraint, Z (1 &lt;= Z &lt;= T). The subsequent Z integers
        (which are unique) list the ingredient(s) whose combination
        disqualifies a pizza from consideration for the cows.

SAMPLE INPUT (file pizza.in):

6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6

INPUT DETAILS:

Six ingredients numbered 1..6. Five constraints: No pizza can contain
ingredient 1, no pizza can contain ingredients numbered 2 and 4, etc.

OUTPUT FORMAT:

* Line 1: A single integer that is the total number of pizzas that can
        be created using the number of ingredients and constraints.

SAMPLE OUTPUT (file pizza.out):

10

OUTPUT DETAILS:

This includes pizzas with: no ingredients; ingr 2; ingr's 2 &amp; 3;
ingr's 2 &amp; 6; ingr 3; ingr's 3 &amp; 4; ingr's 3 &amp; 6; ingr 4; ingr's 4
&amp; 6; and ingr 6.

**********************************************************************

Problem 14: Bedtime Reading, II [Traditional, 2006]

Bessie rubbed her eyes again. "The headache's gone. Can you go
over that part about number chains again, Farmer John?"

"Sure!" FJ exclaimed. "Let's continue with that sigma function, the
one that is the sum of a number's divisors. First, though, let's
exclude the number itself from the sum and call our new function
bess(), in your honor. Now bess(12) = 1+2+3+4+6 = 16. If we continue
and compute bess(16), we find it is 1 + 2 + 4 + 8 = 15. Then bess(15)
= 1 + 3 + 5 = 9 and bess(9) = 1 + 3 = 4. Then bess(4) = 1 + 2 = 3
and bess(3) = 1. For better or worse, bess(1) is 0. Not much of a
chain, really."

"But look," continued FJ. "We see that bess(6) = 1 + 2 + 3 = 6 and
bess(28) = 28. Those form little tiny chains called 'perfect numbers'.
Moving to bigger numbers, bess(220) = 284 and -- get this -- bess(284)
= 220 -- a chain of length 2! Some chains are even longer."

"It's so late; I'm not sure I can do the math," mooed Bessie.

"No problem," said FJ. "We'll ask the programmers to write a program
that accepts a start and end integer (1 &lt;= start &lt;= end &lt;= 1,000,000)
and finds all the possible number chains whose starting value is
in the interval (start..end). No intermediate value is allowed to
exceed 2,000,000, though some might be larger than the 'end' integer.
No chain is longer than 50 elements. Print only chains whose smallest
element comes first (i.e., no intermediate value is less than the
start value of the chain). We must ask them, though, to compute the
answers with their program and not just print them. We'll supply
test data that is reasonable to finish in 1.0 CPU seconds."

PROBLEM NAME: br2

INPUT FORMAT:

* Line 1: Two space-separated integers: start and end

SAMPLE INPUT (file br2.in):

200 1200

OUTPUT FORMAT:

* Lines 1..?: Each line contains a space-separated list that
        represents one chain of numbers calculated using the described
        bess() function.

SAMPLE OUTPUT (file br2.out):

220 284
496
1184 1210

**********************************************************************

Problem 15: Cows on a Leash [Brian Dean and Rob Kolstad, 2006]

Farmer John has forced indignity onto the N (1 &lt;= N &lt;= 32,000) cows:
he has purchased a number of leashes and has leashed the cows to
stakes (conveniently located at integer locations) next to a long,
linear fence that is no longer than 5,300,000 meters and runs
east-west. Every single cow is straining her leash as much as she
can to the east (though never beyond the end of the fence).

Happily, the cows have acquired an ally: FJ's wife thinks that
leashes are barbaric and has come to the fence with her dull butcher
knife. She can perform only a few cuts with it and wants to do the
best job she can. She can locate herself halfway between two integer
points along the fence and cut all the leashes that cross in front
of her at that place.

Given the length of each leash and the location of its stake in the
ground, what is the minimal number of cuts she must perform to free
the cows?

PROBLEM NAME: leash

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Each line contains two space-separated positive
        integers that describe a leash. The first is the location of
        the leash's stake; the second is the length of the leash.

SAMPLE INPUT (file leash.in):

7
2 4
4 7
3 3
5 3
9 4
1 5
7 3

INPUT DETAILS:

Here is a simple graphical representation of the locations of the leashes:
                  1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3
-------------------------
. 111111111 . . . . . . .
. . . 222222222222222 . .
. . 3333333 . . . . . . .
. . . . 4444444 . . . . .
. . . . . . . . 555555555
66666666666 . . . . . . .
. . . . . . 7777777 . . .

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of cuts so that
        each leash is cut at least once.

SAMPLE OUTPUT (file leash.out):

2

OUTPUT DETAILS:

Cutting at 5.5 cuts leashes 1, 2, 3, 4, and 6. A second cut at 9.5 cuts
leashes 5 and 7. Other locations are surely possible, but no single cut can
penetrate leashes 5 and 6, so at least two cuts are necessary.

**********************************************************************

</pre><hr>
<form action="/ioiupload2" enctype="multipart/form-data" method="POST">
<input type="hidden" name="a" value="DNxvLsnwzWL">


<table bgcolor="#000000" cellpadding=0 cellspacing=0 border=0>
<tr><td height=1><td>

<tr><td width=1><td>

<table bgcolor="#bfffbf" cellpadding=5>
<tr><td>Use this form to submit a program for grading:</td>
<td rowspan="3"><input type="submit" VALUE="Submit" name='submit'></td>
<tr><td width=60%><B>Program File:</B><input type="file" NAME="filename"></td>
    </tr>
</table>
</td><td width=1></td>

<tr height=1><td></td></tr>
</table>
<hr>
Nothing is currently saved for grading.
<hr>
<center>
<a href="/ioiedit?a=DNxvLsnwzWL">Edit your database record</a>
&nbsp;|&nbsp;
<a href="/ioiupload2?a=DNxvLsnwzWL&logout=1"> Logout </a>
<!--<a href="https://ace.delos.com/rules.html" target="_blank"> Rules </a>-->
&nbsp;|&nbsp;
<a href=http://ace.delos.com/ioiupload2?init=1&a=DNxvLsnwzWL>Main contest index</a>
</center>
<!--&nbsp;|&nbsp;-->
<center>
<a href=http://ace.delos.com/ioiupload2?a=DNxvLsnwzWL&showsubmit>See submitted solutions</a>
&nbsp;|&nbsp;
<a href=http://ace.delos.com/ioiupload2?a=DNxvLsnwzWL&suggestionbox>Send message
to contest director</a><br>
Director is currently online (AIM: RobAtDelos)<br>
This page was generated at 13:18:11 GMT.
</center>
</body>

